package cn.jdemo.algorithm.dynamicProgramming;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 动规5步
 * 1.定义
 *      dp[i] 爬到i阶楼梯有dp[i]种方法可以爬到楼顶
 * 2.递推公式
 *      dp[i] = dp[i - 1] + dp[i - 2]
 * 3.初始化
 *      dp[0] = 0;
 *      dp[1] = 1;
 *      dp[2] = 2;
 * 4.遍历顺序
 * 5.样例:n = 3
 *          dp[i]
 *      0     0
 *      1     1
 *      2     2
 *      3     3
 */
public class ClimbStairs {
    public static void main(String[] args) {
        int res = new ClimbStairs().climbStairs(3);
        System.out.println(res);
    }


    public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}
